Congestion avoidance techniques are essential to the operation of networks and network devices. One such technique known in the art as “Random Early Discard” or “RED” is described in a publication by S. Floyd and V. Jacobson entitled “Random Early Detection Gateways for Congestion Avoidance,” (Transactions on Networking, August 1993) (the “Floyd and Jacobson paper”), which is hereby incorporated by reference for all purposes.
The basic principle behind RED is to control the average length of a network device's (e.g., a router's) output queue in order to avoid long term congestion. To achieve this goal, RED must work with transport protocols, such as TCP, which are equipped with their own congestion avoidance mechanisms and are thus capable to react to congestion indications generated by devices implementing RED. The RED algorithm has been implemented in some output-buffered network devices, including the Catalyst 6500 switch and the 7200 series router provided by Cisco Systems, Inc., to prevent congestion of output buffers.
Graph 100 of FIG. 1A illustrates the operation of RED. For each incoming packet, the average queue length is calculated. (Please note that the terms “packet” and “frame” may be used interchangeably herein.) If the average queue length is below a predefined minimum threshold 105, the packet is accepted and stored in the output queue for transmission. If the average queue size is above the minimum threshold 105 but below a predefined maximum threshold 110, a packet marking probability is computed and the packet gets marked according to this probability. The marking probability is proportional to the average queue size. Therefore, when the queue is larger, there is a higher probability for an incoming packet to get marked or dropped. Finally, if the average queue size is above the maximum threshold 110, all incoming packets are marked or dropped until the average queue size falls again below the maximum threshold 110.
It is responsibility of the transport protocol to take the appropriate countermeasures when it detects packets marked by RED. When TCP is being used in the absence of an explicit method of marking packets, packets can only be “marked” by discarding them, with TCP interpreting the loss of packets as a congestion indication. When a TCP source detects only a few dropped packets, it can recover via a “fast retransmit,” wherein its transmission rate is reduced by half.
However, service providers must apply other network controls in order to regulate or “police” various aspects of network traffic. For example, network administrators need to ensure that network resources are allocated in a fair and predictable manner, while still allowing customers to transmit bursts of data when appropriate. Therefore, many network devices also apply some form of policing method in addition to RED (or in addition to a modified version of RED).
For example, FIG. 1B illustrates the operation of token bucket 150 according to one such policing method. Each of tokens 185 may be considered an authorization for transmitting a predetermined unit of data; therefore, tokens are usually measured in bits or bytes. Tokens 185, which are represented as drops in FIG. 1B, flow into token bucket 150 at a fixed rate R, which is measured in data units per time unit (e.g., bits per second).
Token bucket 150 has a capacity 190. In this example, token bucket 150 has a capacity of BMAX data units. Capacity BMAX is also referred to as the “burst size” of token bucket 150, because it is equal to the maximum data burst allowed by controller 192. Accordingly, token bucket 150 allows data bursts, but places limits on how bursty traffic can be.
Instantaneous token bucket level B1 160 is a measure of the number of tokens or data units in token bucket 150 at any given time. In this example there is no physical queue associated with token bucket 150. Controller 192 will cause an incoming packet to be dropped immediately if there are insufficient tokens in token bucket 150 to permit transmission of the packet. In other words, if incoming packet 196 were larger than B1 data units, packet 196 would be dropped.
Other policing methods, similar to the one just described, have been introduced in the past. Examples include two methods that are discussed in “Traffic Management Specification” Versions 4.0 and 4.1 (The ATM Forum Technical Committee 1996), under the names of Virtual Scheduling and Continuous-State Leaky Bucket Algorithm, respectively, which are hereby incorporated by reference. In the cited references, these schemes apply to the case of ATM networking, but have been generalized to the case of general packet networks.
In other policing methods, however, there may be an associated buffer. A certain number of packets could accumulate in the buffer until there are enough tokens in the token bucket 150 to permit the data to be transmitted. However, when the buffer is full, all incoming packets will be dropped. This is a “tail drop” or “tail discard” method that was once commonly used in network devices.
Whether or not incoming packets are buffered, packets will eventually be dropped when they are arriving faster than R, the rate at which token bucket 150 (or the like) is replenished. When many successive packets are dropped, this will cause TCP senders to go into a “timeout” that may last on the order of hundreds of milliseconds. Long-lived TCP senders respond much more satisfactorily to RED (or the like) than to “tail drop” methods.
Therefore, some of the potential advantages of implementing RED in a network device are not realized because prior art policing methods are also being implemented in the same device. It would be desirable to implement methods and devices that overcome at least some of the aforementioned shortcomings of the prior art.